package leetcode_900;

/**
 *@author 周杨
 *MinimumNumberOfRefuelingStops_871_  给定初始燃油数量和目的地 还有若干加油站 的距离和油量  那么问能否到达目的地 如果能 那么最少加多少油
 *describe:用动态规划 AC 30%
 *2018年11月7日 上午10:22:17
 */
public class MinimumNumberOfRefuelingStops_871_ {
	/**
	 * describe:动态规划 因为问题规模只有500 那么不断用dp[i]更新 加i次油 能到达的最大油数
	 * 2018年11月7日 上午10:17:31
	 */
	public int minRefuelStops(int target, int startFuel, int[][] stations) {
		long dp[]=new long[stations.length+1];
		dp[0]=startFuel;//初始 dp[i]表示加i次油 能达到最大油数
		for(int i=0;i<stations.length;++i) {
			for(int j=i;j>=0;--j) {//第i个加油站  最多加i+1次油 
				if(dp[j]>=stations[i][0])//可以到达这个加油站
					dp[j+1]=Math.max(dp[j+1], dp[j]+(long)stations[i][1]);//更新最优解
			}
		}
		for(int i=0;i<dp.length;++i)
			if(dp[i]>=target)
				return i;
		return -1;
	}
}
